{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #验证外星语词典"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isAlienSorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证外星语词典"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某种外星语也使用英文小写字母，但可能顺序 <code>order</code> 不同。字母表的顺序（<code>order</code>）是一些小写字母的排列。</p>\n",
    "\n",
    "<p>给定一组用外星语书写的单词 <code>words</code>，以及其字母表的顺序 <code>order</code>，只有当给定的单词在这种外星语中按字典序排列时，返回 <code>true</code>；否则，返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [&quot;hello&quot;,&quot;leetcode&quot;], order = &quot;hlabcdefgijkmnopqrstuvwxyz&quot;\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>在该语言的字母表中，&#39;h&#39; 位于 &#39;l&#39; 之前，所以单词序列是按字典序排列的。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [&quot;word&quot;,&quot;world&quot;,&quot;row&quot;], order = &quot;worldabcefghijkmnpqstuvxyz&quot;\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>在该语言的字母表中，&#39;d&#39; 位于 &#39;l&#39; 之后，那么 words[0] &gt; words[1]，因此单词序列不是按字典序排列的。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [&quot;apple&quot;,&quot;app&quot;], order = &quot;abcdefghijklmnopqrstuvwxyz&quot;\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>当前三个字符 &quot;app&quot; 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 &quot;apple&quot; &gt; &quot;app&quot;，因为 &#39;l&#39; &gt; &#39;&empty;&#39;，其中 &#39;&empty;&#39; 是空白字符，定义为比任何其他字符都小（<a href=\"https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E5%BA%8F\" target=\"_blank\">更多信息</a>）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 20</code></li>\n",
    "\t<li><code>order.length == 26</code></li>\n",
    "\t<li>在&nbsp;<code>words[i]</code>&nbsp;和&nbsp;<code>order</code>&nbsp;中的所有字符都是英文小写字母。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 953&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/verifying-an-alien-dictionary/\">https://leetcode-cn.com/problems/verifying-an-alien-dictionary/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lwyVBB](https://leetcode.cn/problems/lwyVBB/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lwyVBB](https://leetcode.cn/problems/lwyVBB/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"hello\",\"leetcode\"]\\n\"hlabcdefgijkmnopqrstuvwxyz\"', '[\"word\",\"world\",\"row\"]\\n\"worldabcefghijkmnpqstuvxyz\"', '[\"apple\",\"app\"]\\n\"abcdefghijklmnopqrstuvwxyz\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        \n",
    "        d = dict()\n",
    "        rec = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        for i in range(26):\n",
    "            d[order[i]] = rec[i]\n",
    "        \n",
    "        def change(word):\n",
    "            rword = []\n",
    "            for i in word:\n",
    "                rword.append(d[i])\n",
    "            return ''.join(rword)\n",
    "        \n",
    "        rword = [change(i) for i in words]\n",
    "        rrword = sorted(rword)\n",
    "        if rrword == rword:\n",
    "            return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        x=[]\n",
    "        for i in range(len(words)-1):\n",
    "            if False not in x:\n",
    "                for j in range(len(words[i])):\n",
    "                    if j==len(words[i+1]):\n",
    "                        x.append(False)\n",
    "                        break\n",
    "                    elif order.index(words[i][j])<order.index(words[i+1][j]):\n",
    "                        break\n",
    "                    elif order.index(words[i][j])>order.index(words[i+1][j]):\n",
    "                        x.append(False)\n",
    "                        break\n",
    "            else:\n",
    "                break\n",
    "        return True in x or x==[]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        # 思路：这道题题意比较难理解，它是要分析2个单词的子母，从头开始比较\n",
    "        # 如果前大后小，直接False，如果前小后大， 则再遍历下2个单词\n",
    "        # 如果2个单词的子母相等，则比较下一个子母\n",
    "        dic = {}\n",
    "        for k, v in enumerate(order):\n",
    "            dic[v] = k\n",
    "        for i in range(len(words) - 1):\n",
    "            tmp1 = words[i]\n",
    "            tmp2 = words[i + 1]\n",
    "            for j in range(max(len(tmp1), len(tmp2))):\n",
    "                # 谁先遍历完，谁就赋小值，比如-1，方便下一轮比较\n",
    "                idx1 = dic[tmp1[j]] if j < len(tmp1) else -1\n",
    "                idx2 = dic[tmp2[j]] if j < len(tmp2) else -1\n",
    "                if idx1 > idx2:\n",
    "                    return False\n",
    "                elif idx1 < idx2:\n",
    "                    break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        def o(word1,word2):\n",
    "            for i in range(min(len(word1),len(word2))):\n",
    "                if order.index(word1[i])<order.index(word2[i]):\n",
    "                    return True\n",
    "                elif order.index(word1[i])>order.index(word2[i]):\n",
    "                    return False\n",
    "            return len(word1)<=len(word2)\n",
    "        for i in range(1,len(words)):\n",
    "            if not o(words[i-1],words[i]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        # 思路：这道题题意比较难理解，它是要分析2个单词的子母，从头开始比较\n",
    "        # 如果前大后小，直接False，如果前小后大， 则再遍历下2个单词\n",
    "        # 如果2个单词的子母相等，则比较下一个子母\n",
    "        dic = {}\n",
    "        for k, v in enumerate(order):\n",
    "            dic[v] = k\n",
    "        for i in range(len(words) - 1):\n",
    "            tmp1 = words[i]\n",
    "            tmp2 = words[i + 1]\n",
    "            for j in range(max(len(tmp1), len(tmp2))):\n",
    "                idx1 = dic[tmp1[j]] if j < len(tmp1) else -1\n",
    "                idx2 = dic[tmp2[j]] if j < len(tmp2) else -1\n",
    "                if idx1 > idx2:\n",
    "                    return False\n",
    "                elif idx1 < idx2:\n",
    "                    break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {}\n",
    "        for i in range(len(order)):\n",
    "            dic[order[i]] = i\n",
    "        for i in range(1, len(words)):\n",
    "            isvalid = False\n",
    "            for j in range(min(len(words[i-1]), len(words[i]))):\n",
    "                prev, cur = words[i-1][j], words[i][j]\n",
    "                if dic[prev] == dic[cur]:\n",
    "                    continue\n",
    "                elif dic[prev] < dic[cur]:\n",
    "                    isvalid = True\n",
    "                    break\n",
    "                else:\n",
    "                    return False\n",
    "            if isvalid == False and len(words[i-1]) > len(words[i]):\n",
    "                return False\n",
    "            \n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        order_dic = dict()\n",
    "        for i in range(len(order)):\n",
    "            order_dic[order[i]] =  i\n",
    "        if  len(words)<=1:\n",
    "            return True\n",
    "        def is_check(ward1,word2)->bool:\n",
    "            for w1,w2 in zip(ward1,word2):\n",
    "                if order_dic[w1] <order_dic[w2]:\n",
    "                    return True\n",
    "                elif  order_dic[w1] == order_dic[w2]:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            if  len(ward1)<= len(word2):\n",
    "                return True\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            if not is_check(words[i],words[i+1]):\n",
    "                print(i)\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "      index = {c:i for i, c in enumerate(order)}\n",
    "      for w1, w2 in pairwise(words):\n",
    "        for a, b in zip_longest(w1, w2):\n",
    "          if a is None:\n",
    "            break\n",
    "          if b is None:\n",
    "            return False\n",
    "          idx1, idx2 = index[a], index[b]\n",
    "          if idx1 < idx2:\n",
    "            break\n",
    "          elif idx1 > idx2:\n",
    "            return False\n",
    "      return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = {j:i for i, j in enumerate(order)}\n",
    "        for i in range(len(words) - 1):\n",
    "            w1, w1_len = words[i], len(words[i])\n",
    "            w2, w2_len = words[i + 1], len(words[i + 1])\n",
    "            for idx in range(max(w1_len, w2_len)):\n",
    "                w1_idx = -1 if idx >= w1_len else d[w1[idx]]\n",
    "                w2_idx = -1 if idx >= w2_len else d[w2[idx]]\n",
    "                if w1_idx > w2_idx:\n",
    "                    return False\n",
    "                elif w1_idx < w2_idx:\n",
    "                    break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = {order[i]:i for i in range(len(order))}\n",
    "        for i in range(1, len(words)):\n",
    "            word1 = words[i-1]\n",
    "            word2 = words[i]\n",
    "            i, j = 0, 0\n",
    "            while i < len(word1) and j < len(word2):\n",
    "                if d[word1[i]] < d[word2[j]]:\n",
    "                    break\n",
    "                elif d[word1[i]] == d[word2[j]]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "            if i < len(word1) and j == len(word2):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        # 输入：words = [\"word\",\"world\",\"row\"], order = \"worldabcefghijkmnpqstuvxyz\"\n",
    "        # 输出：false\n",
    "        # 解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。\n",
    "        def compare(this, that):\n",
    "            for c_this, c_that in zip(this, that):\n",
    "                if order_mapping[c_this] > order_mapping[c_that]: return True\n",
    "                elif order_mapping[c_this] < order_mapping[c_that]: return False\n",
    "            if len(this) > len(that): return True\n",
    "            return False\n",
    "\n",
    "        order_mapping = {}\n",
    "        for i, c in enumerate(order):\n",
    "            order_mapping[c] = i\n",
    "        for i in range(len(words) - 1):\n",
    "            this = words[i]\n",
    "            that = words[i + 1]\n",
    "            if compare(this, that): return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        record = {}\n",
    "        for i, c in enumerate(order):\n",
    "            record[c] = i\n",
    "        n = len(words)\n",
    "        for i in range(n-1):\n",
    "            m1, m2, flag = len(words[i]), len(words[i+1]), False\n",
    "            for j in range(min(m1, m2)):\n",
    "                if record[words[i][j]] < record[words[i+1][j]]:\n",
    "                    flag = True\n",
    "                    break\n",
    "                elif record[words[i][j]] > record[words[i+1][j]]:\n",
    "                    return False\n",
    "            if not flag:\n",
    "                if m1 > m2:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        for a, b in zip(words[0:-1], words[1:]):\n",
    "            N = min(len(a), len(b))\n",
    "            for i in range(N):\n",
    "                ca = a[i]\n",
    "                cb = b[i]\n",
    "                ia = order.index(ca)\n",
    "                ib = order.index(cb)\n",
    "                if ia > ib:\n",
    "                    return False\n",
    "                if ia < ib:\n",
    "                    break\n",
    "            else:\n",
    "                if len(a) > len(b):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c:i for i,c in enumerate(order)}\n",
    "        for i in range(len(words)-1):\n",
    "            w1,w2 = words[i],words[i+1]\n",
    "            l1 = len(w1)\n",
    "            l2 = len(w2)\n",
    "            flag = False\n",
    "            for j in range(max(l1,l2)):\n",
    "                i1 = -1 if j>=l1 else index[w1[j]]\n",
    "                i2 = -1 if j>=l2 else index[w2[j]]\n",
    "                if i1>i2:\n",
    "                    return False\n",
    "                if i1<i2:\n",
    "                    break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        def compare(word_i, word_j, index_i=0, index_j=0):\n",
    "            # word_i[index_i]空字符，返回True；word_j[index_j]空字符，返回False\n",
    "            if index_i >= len(word_i):\n",
    "                return True\n",
    "            if index_j >= len(word_j):\n",
    "                return False\n",
    "            # 字符相等，比较下一个\n",
    "            if word_i[index_i] == word_j[index_j]:\n",
    "                return compare(word_i, word_j, index_i + 1, index_j + 1)\n",
    "            # 字符不等，比较在order的次序\n",
    "            ix1 = order.index(word_i[index_i])\n",
    "            ix2 = order.index(word_j[index_j])\n",
    "            return ix1 < ix2\n",
    "        \n",
    "        for index in range(1, len(words)):\n",
    "            if not compare(words[index - 1], words[index]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "\n",
    "        mp = {c:i for i, c in enumerate(order)}\n",
    "        n = len(words)\n",
    "        for i in range(1, n):\n",
    "            s1 = words[i-1]\n",
    "            s2 = words[i]\n",
    "\n",
    "            valid = False\n",
    "            j = 0\n",
    "            while j < len(s1) and j < len(s2):\n",
    "                if mp[s1[j]] < mp[s2[j]]:\n",
    "                    valid = True\n",
    "                    break\n",
    "                elif mp[s1[j]] > mp[s2[j]]:\n",
    "                    return False\n",
    "                j += 1\n",
    "            if not valid:\n",
    "                if len(s1) > len(s2):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = dict()\n",
    "        for i,v in enumerate(order):\n",
    "            d[v] = i\n",
    "        for i in range(len(words) - 1):\n",
    "            w1, w1Len  =  words[i], len(words[i])\n",
    "            w2, w2Len  =  words[i + 1], len(words[i + 1])\n",
    "            for j in range(max(w1Len, w2Len)):\n",
    "                x = -1 if j>= w1Len else d[w1[j]]\n",
    "                y = -1 if j>= w2Len else d[w2[j]]\n",
    "                if x > y:\n",
    "                    return False\n",
    "                if x < y:\n",
    "                    break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        char2idx = {c: i for i, c in enumerate(order)}\n",
    "\n",
    "        def cmp(s1, s2):\n",
    "            for c1, c2 in zip(s1, s2):\n",
    "                if c1 != c2:\n",
    "                    return char2idx[c1] - char2idx[c2]\n",
    "            \n",
    "            return len(s1) - len(s2)\n",
    "        \n",
    "        sorted_words = sorted(words, key=functools.cmp_to_key(cmp))\n",
    "\n",
    "        for i in range(len(words)):\n",
    "            if words[i] != sorted_words[i]:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c:i for i, c in enumerate(order)}\n",
    "        return all(s<=t for s, t in pairwise([index[c] for c in word]for word in words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        def judge(w1,w2,order):\n",
    "            ds = {v:i for i,v in enumerate(order)}\n",
    "            l1,l2 = len(w1),len(w2)\n",
    "            for i in range(l1):\n",
    "                if i > l2-1 or ds[w1[i]] > ds[w2[i]]:\n",
    "                    return False\n",
    "                elif ds[w1[i]] < ds[w2[i]]:\n",
    "                    return True\n",
    "            return True\n",
    "        \n",
    "        return all(judge(words[i],words[i+1],order) for i in range(len(words)-1))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.order_dic = {}\n",
    "\n",
    "    def compare_two_words(self, words1: str, words2: str) -> bool:\n",
    "        length = min(len(words1), len(words2))\n",
    "        for k in range(length):\n",
    "            if self.order_dic[words1[k]] < self.order_dic[words2[k]]:\n",
    "                return True\n",
    "            if self.order_dic[words1[k]] == self.order_dic[words2[k]]:\n",
    "                continue\n",
    "            if self.order_dic[words1[k]] > self.order_dic[words2[k]]:\n",
    "                return False\n",
    "        if len(words1) > len(words2):\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def compare_words(self, words: List[str]) -> bool:\n",
    "        res = True\n",
    "        for j in range(len(words) - 1):\n",
    "            length = min(len(words[j]), len(words[j+1]))\n",
    "            if self.compare_two_words(words[j], words[j+1]) == False:\n",
    "                return False\n",
    "\n",
    "        return res\n",
    "\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        for i in range(len(order)):\n",
    "            self.order_dic[order[i]] = i\n",
    "        res = self.compare_words(words)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = {x: i for i, x in enumerate(order)}\n",
    "        return all(s<=t for s, t in pairwise([d[c] for c in word] for word in words))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        # a~z字典、转换\n",
    "        abc = ''.join([chr(i) for i in range(97,122+1)])\n",
    "        trans_table = str.maketrans(order,abc)\n",
    "        words_c = [i.translate(trans_table) for i in words]\n",
    "        print(f'翻译后的：{words_c}，排序后的：{sorted(words_c)}')\n",
    "        return words_c == sorted(words_c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {}\n",
    "        for i, x in enumerate(order):\n",
    "            dic[x] = i\n",
    "        def compare(a, b):\n",
    "            n = len(a)\n",
    "            m = len(b)\n",
    "            i = 0\n",
    "            while i < min(m,n):\n",
    "                if dic[a[i]] > dic[b[i]]:\n",
    "                    return False\n",
    "                if dic[a[i]] < dic[b[i]]:\n",
    "                    return True\n",
    "                i += 1\n",
    "            if n <= m:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        for i in range(len(words)-1):\n",
    "            if not compare(words[i], words[i+1]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {}\n",
    "        for index, value in enumerate(order):\n",
    "            dic[value] = index\n",
    "        # print(dic)\n",
    "        word = ''.join(words)\n",
    "        # print(word)\n",
    "        dd = {value: index for index, value in enumerate(word)}\n",
    "        count = 0\n",
    "        n = len(word)\n",
    "        return all([dic[w] for w in words[i - 1]] <= [dic[w] for w in words[i]] for i in\n",
    "                           range(1, len(words)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        hashmap = dict()\n",
    "        for i, word in enumerate(order):\n",
    "            hashmap[word] = i\n",
    "\n",
    "        def battle(a:str, b:str) -> bool:\n",
    "            m, n = len(a), len(b)\n",
    "            h = min(m, n)\n",
    "            for i in range(h):\n",
    "                if hashmap[a[i]] > hashmap[b[i]]: return False\n",
    "                if hashmap[a[i]] < hashmap[b[i]]: return True\n",
    "            if m <= n: return True\n",
    "            else: return False\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            if battle(words[i], words[i+1]) == False:\n",
    "                return False\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        n = len(words)\n",
    "\n",
    "        for i in range(n-1):\n",
    "            a,b = len(words[i]), len(words[i+1])\n",
    "            m = min(len(words[i]), len(words[i+1]))\n",
    "            for j in range(m):\n",
    "                if order.index(words[i][j]) > order.index(words[i+1][j]):\n",
    "                    return False\n",
    "                elif order.index(words[i][j]) < order.index(words[i+1][j]):\n",
    "                    break\n",
    "                if j == m-1 and a > b:\n",
    "                    return False\n",
    "\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        alien_dict = {}\n",
    "        for i, e in enumerate(order):\n",
    "            alien_dict[e] = chr(ord('a') + i)\n",
    "        list1 = list()\n",
    "        for word in words:\n",
    "            list2 = list(word)\n",
    "            for i, e in enumerate(list2):\n",
    "                list2[i] = alien_dict.get(e)\n",
    "            list1.append(''.join(list2))\n",
    "        list3 = copy.deepcopy(list1)\n",
    "        list3.sort()\n",
    "        return list1.__eq__(list3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        for i in range(len(words) - 1):\n",
    "            w1, w2 = words[i], words[i + 1]\n",
    "            l1, l2 = len(w1), len(w2)\n",
    "            flag = False\n",
    "            for j in range(max(l1, l2)):\n",
    "                i1, i2 = -1 if j >= l1 else index[w1[j]], -1 if j >= l2 else index[w2[j]]\n",
    "                if i1 > i2:\n",
    "                    # 说明不是按字典序排序，直接返回False\n",
    "                    return False\n",
    "                if i1 < i2:\n",
    "                    # 说明当前两单词是按字典序排序，无需再往下进行循环比较\n",
    "                    break\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        def judge(w1,w2,order):\n",
    "            ds = {v:i for i,v in enumerate(order)}\n",
    "            l1,l2 = len(w1),len(w2)\n",
    "            for i in range(l1):\n",
    "                if i > l2-1 or ds[w1[i]] > ds[w2[i]]:\n",
    "                    return False\n",
    "                elif ds[w1[i]] < ds[w2[i]]:\n",
    "                    return True\n",
    "            return True\n",
    "        \n",
    "        return all(judge(words[i],words[i+1],order) for i in range(len(words)-1))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        orders = {ch:idx for idx,ch in enumerate(order)}\n",
    "\n",
    "        # 暴力\n",
    "        for i in range(len(words) - 1):\n",
    "            w1 , w2 = words[i],words[i + 1]\n",
    "            l1 , l2 = len(w1),len(w2)\n",
    "            for j in range(max(l1,l2)):\n",
    "                # 逐位判断\n",
    "                r1 = -1 if j >= l1 else orders[w1[j]]\n",
    "                r2 = -1 if j >= l2 else orders[w2[j]]\n",
    "                if r1 > r2:\n",
    "                    return False\n",
    "\n",
    "                if r1 < r2:\n",
    "                    break\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "      for w1, w2 in pairwise(words):\n",
    "        for a, b in zip_longest(w1, w2):\n",
    "          if a is None:\n",
    "            break\n",
    "          if b is None:\n",
    "            return False\n",
    "          idx1, idx2 = order.index(a), order.index(b)\n",
    "          if idx1 < idx2:\n",
    "            break\n",
    "          elif idx1 > idx2:\n",
    "            return False\n",
    "      return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        ds = {v:i for i,v in enumerate(order)}\n",
    "        ts = sorted(words,key = lambda x:[ds[x[idx]] for idx in range(len(x))])\n",
    "        return ts == words            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        calc = {i:j for j,i in enumerate(order)}\n",
    "        for i in range(len(words)-1):\n",
    "            wrd_1,wrd_1_len = words[i],len(words[i])\n",
    "            wrd_2,wrd_2_len = words[i+1],len(words[i+1])\n",
    "            #作比较\n",
    "            for index in range(max(wrd_1_len,wrd_2_len)):\n",
    "                wrd_1_index = -1 if index >= wrd_1_len else calc[wrd_1[index]] # -1是单词后面如果相比较有空，则为-1\n",
    "                wrd_2_index = -1 if index >= wrd_2_len else calc[wrd_2[index]]\n",
    "                if wrd_1_index > wrd_2_index:\n",
    "                    return False\n",
    "                # 如果已经小了后面就不需要比了\n",
    "                if wrd_1_index < wrd_2_index: \n",
    "                    break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {j: i for i, j in enumerate(order)}\n",
    "        for i in range(len(words) - 1):\n",
    "            w1, w1_len = words[i], len(words[i])\n",
    "            w2, w2_len = words[i + 1], len(words[i + 1])\n",
    "            for idx in range(max(w1_len, w2_len)):\n",
    "                w1_idx = -1 if idx >= w1_len else dic[w1[idx]]\n",
    "                w2_idx = -1 if idx >= w2_len else dic[w2[idx]]\n",
    "                if w1_idx > w2_idx:\n",
    "                    return False\n",
    "                if w1_idx < w2_idx:\n",
    "                    break\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c:i for i, c in enumerate(order)}\n",
    "        # 将单词转换为索引列表，并用pairwise生成相邻元素对\n",
    "        dict_order = pairwise([index[c] for c in word] for word in words)\n",
    "        return all(s <= t for s, t in dict_order)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {j: i for i, j in enumerate(order)}\n",
    "        for i in range(len(words) - 1):\n",
    "            w1, w1_len = words[i], len(words[i])\n",
    "            w2, w2_len = words[i + 1], len(words[i + 1])\n",
    "            for idx in range(max(w1_len, w2_len)):\n",
    "                w1_idx = -1 if idx >=w1_len else dic[w1[idx]]\n",
    "                w2_idx = -1 if idx >=w2_len else dic[w2[idx]]\n",
    "                if w1_idx > w2_idx:\n",
    "                    return False\n",
    "                if w1_idx < w2_idx:\n",
    "                    break\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        n = len(words)\n",
    "        mp = [0]*26\n",
    "        for i, o in enumerate(order):\n",
    "            index = ord(o) - ord(\"a\")\n",
    "            mp[index] = - i\n",
    "        for i in range(1, n):\n",
    "            pre = words[i-1]\n",
    "            cur = words[i]\n",
    "            for j in range(len(pre)):\n",
    "                if j >= len(cur):\n",
    "                    return False\n",
    "                pl = ord(pre[j]) - ord(\"a\")\n",
    "                cl = ord(cur[j]) - ord(\"a\")\n",
    "                if mp[pl] < mp[cl]:\n",
    "                    return False\n",
    "                elif mp[pl] == mp[cl]:\n",
    "                    continue\n",
    "                else:\n",
    "                    break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        if len(words) == 1:\n",
    "            return True\n",
    "        # parse order\n",
    "        order_dict = {}\n",
    "        for i,char in enumerate(order):\n",
    "            order_dict[char] = i\n",
    "        for i in range(1,len(words)):\n",
    "            if len(words[i]) < len(words[i-1]) and words[i-1][:len(words[i])] == words[i]:\n",
    "                return False\n",
    "            for j in range(min(len(words[i-1]),len(words[i]))):\n",
    "                if words[i-1][j] != words[i][j]:\n",
    "                    char_prev = words[i-1][j]\n",
    "                    char_now = words[i][j]\n",
    "                    if order_dict[char_prev] <= order_dict[char_now]:\n",
    "                        break\n",
    "                    else:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        ds = {v:i for i,v in enumerate(order)}\n",
    "        ts = sorted(words,key = lambda x:[ds[x[idx]] for idx in range(len(x))])\n",
    "        return ts == words            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "    def kFun(x):\n",
    "        ret = []\n",
    "        for c in x:\n",
    "          ret.append(order.index(c))\n",
    "        return tuple(ret)\n",
    "    orig = words.copy()\n",
    "    words.sort(key = kFun)\n",
    "    return orig == words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        n, m = len(words), len(order)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        d = {}\n",
    "        for i, c in enumerate(order):\n",
    "            d[c] = i\n",
    "        \n",
    "        for w1, w2 in pairwise(words):\n",
    "            valid = True\n",
    "            for a,b in zip(w1, w2):\n",
    "                if a != b:\n",
    "                    if d[a] < d[b]:\n",
    "                        valid = False\n",
    "                        break\n",
    "                    else:\n",
    "                        return False\n",
    "            if valid and len(w1) > len(w2):\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        wordMap = {value: idx for idx, value in enumerate(order)}\n",
    "        prev = [wordMap[w] for w in words[0]]\n",
    "\n",
    "        for word in words[1:]:\n",
    "            curr = [wordMap[w] for w in word]\n",
    "            if prev > curr:\n",
    "                return False \n",
    "            prev = curr \n",
    "        \n",
    "        return True \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {j:i for i,j in enumerate(order)}\n",
    "        for i in range(len(words) - 1):\n",
    "            w1, w1_len = words[i], len(words[i])\n",
    "            w2, w2_len = words[i + 1], len(words[i + 1])\n",
    "            for j in range(max(w1_len, w2_len)):\n",
    "                if j >= w1_len:\n",
    "                    w1_idx = -1\n",
    "                else:\n",
    "                    w1_idx = dic[w1[j]]\n",
    "                if j >= w2_len:\n",
    "                    w2_idx = -1\n",
    "                else:\n",
    "                    w2_idx = dic[w2[j]]\n",
    "                if w1_idx > w2_idx:\n",
    "                    return False\n",
    "                elif w1_idx < w2_idx:\n",
    "                    break\n",
    "        \n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        if len(words) == 1:\n",
    "            return True\n",
    "        # parse order\n",
    "        order_dict = {}\n",
    "        for i,char in enumerate(order):\n",
    "            order_dict[char] = i\n",
    "        for i in range(1,len(words)):\n",
    "            if len(words[i]) < len(words[i-1]) and words[i-1][:len(words[i])] == words[i]:\n",
    "                return False\n",
    "            for j in range(min(len(words[i-1]),len(words[i]))):\n",
    "                if words[i-1][j] != words[i][j]:\n",
    "                    char_prev = words[i-1][j]\n",
    "                    char_now = words[i][j]\n",
    "                    if order_dict[char_prev] < order_dict[char_now]:\n",
    "                        break\n",
    "                    else:\n",
    "                        return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
